﻿#include<stdio.h>
#include<stdlib.h>
struct Node {
	int val;
	struct Node* next;
	struct Node* random;
};
struct Node* copyRandomList(struct Node* head)
{
	struct Node* cur = head;
	struct Node* copy = NULL;
	while (cur)
	{
		copy = (struct Node*)malloc(sizeof(struct Node));
		copy->next = cur->next;
		cur->next = copy;
		copy->val = cur->val;
		copy->random = NULL;

		cur = copy->next;
	}
	cur = head;
	while (cur)
	{
		copy = cur->next;
		if (cur->random == NULL)
		{
			copy->random = NULL;
		}
		else
		{
			copy->random = cur->random->next;
		}
		cur = copy->next;
	}
	cur = cur->next;
	copy = cur->next;
	struct Node* newhead = NULL;
	struct Node* newptil = NULL;
	while (cur)
	{
		if (newhead == newptil == NULL)
		{
			newhead = newptil = copy;
		}
		else
		{
			newptil->next = copy;
			newptil = copy;
		}
		copy = cur->next;
		cur = copy->next;
	}
	return newhead;
}
int main()
{
	struct Node* node0 = (struct Node*)malloc(sizeof(struct Node));
	node0->val = 3;
	struct Node* node1 = (struct Node*)malloc(sizeof(struct Node));
	node1->val = 3;
	struct Node* node2 = (struct Node*)malloc(sizeof(struct Node));
	node2->val = 3;

	node0->next = node1;
	node1->next = node2;
	node0->random = NULL;
	node1->random = node0;
	node2->random = NULL;
	return 0;
}